//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#include <buola/utility/cregion.h>

namespace buola {

struct CNewRegion
{
    CNewRegion(std::size_t pCapacity)
        :   mData(alloc_array<CRect_i>(pCapacity))
        ,   mCount(0)
        ,   mCapacity(pCapacity)
    {}

    void Check(std::size_t pAdditional)
    {
        if(mCount+pAdditional>mCapacity)
            realloc_array(mData,mCount*2+pAdditional);
    }
    
    CRect_i *mData;
    std::size_t mCount;
    std::size_t mCapacity;
};

static inline const CRect_i *band_end(const CRect_i *pB,const CRect_i *pE)
{
    const CRect_i *lB=pB;
    while(lB!=pE&&lB->t==pB->t) lB++;
    return lB;
}

static inline void coalesce(CNewRegion &pNew,std::size_t &pPrev,std::size_t &pCur)
{
    std::size_t lSize=pNew.mCount-pCur;
    if(!lSize) return;

    if(pCur-pPrev!=lSize||pNew.mData[pPrev].b!=pNew.mData[pCur].t)
    {
        pPrev=pCur;
        pCur=pNew.mCount;
        return;
    }
    
    for(int i=0;i<lSize;i++)
    {
        if(pNew.mData[pPrev+i].l!=pNew.mData[pCur+i].l||pNew.mData[pPrev+i].r!=pNew.mData[pCur+i].r)
        {
            pPrev=pCur;
            pCur=pNew.mCount;
            return;
        }
    }
    
    for(int i=0;i<lSize;i++)
    {
        pNew.mData[pPrev+i].b=pNew.mData[pCur].b;
    }
    
    pNew.mCount-=lSize;
}

static inline void copy_band(const CRect_i *pSB,const CRect_i *pSE,CNewRegion &pNew,int pTop,int pBottom)
{
    pNew.Check(pSE-pSB);

    for(const CRect_i *lS=pSB;lS!=pSE;lS++)
    {
        pNew.mData[pNew.mCount++]={lS->l,pTop,lS->r,pBottom};
    }
}

static inline void union_rect(const CRect_i &pR,CNewRegion &pNew,bool &pAdded)
{
    if(pAdded&&pNew.mData[pNew.mCount-1].r>=pR.l)
    {
        if(pNew.mData[pNew.mCount-1].r<pR.r)
            pNew.mData[pNew.mCount-1].r=pR.r;
    }
    else
    {
        pNew.Check(1);
        pNew.mData[pNew.mCount++]=pR;
        pAdded=true;
    }
}

static inline void union_band(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E,CNewRegion &pNew,
                              int pTop,int pBottom)
{
    bool lAdded=false;

    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    while(l1!=p1E&&l2!=p2E)
    {
        if(l1->l<l2->l)
        {
            union_rect(CRect_i(l1->l,pTop,l1->r,pBottom),pNew,lAdded);
            l1++;
        }
        else
        {
            union_rect(CRect_i(l2->l,pTop,l2->r,pBottom),pNew,lAdded);
            l2++;
        }
    }
    
    if(l1!=p1E)
    {
        do
        {
            union_rect(CRect_i(l1->l,pTop,l1->r,pBottom),pNew,lAdded);
        } while(++l1!=p1E);    
    }
    else if(l2!=p2E)
    {
        do
        {
            union_rect(CRect_i(l2->l,pTop,l2->r,pBottom),pNew,lAdded);
        } while(++l2!=p2E);
    }
}

static inline void subtract_band(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E,CNewRegion &pNew,
                              int pTop,int pBottom)
{
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    int lX1=l1->l;
    
    if(l1==p1E) return;
    
    while(l2!=p2E)
    {
        if(l2->r<=lX1)
        {
            l2++;
        }
        else if(l2->l<=lX1)
        {
            lX1=l2->r;
            
            if(lX1>=l1->r)
            {
                if(++l1==p1E) return;
                lX1=l1->l;
            }
            else
            {
                l2++;
            }
        }
        else if(l2->l<l1->r)
        {
            pNew.Check(1);
            pNew.mData[pNew.mCount++]={lX1,pTop,l2->l,pBottom};
            lX1=l2->r;
            
            if(lX1>=l1->r)
            {
                if(++l1==p1E) return;
                lX1=l1->l;
            }
            else
            {
                l2++;
            }
        }
        else
        {
            if(l1->r>lX1)
            {
                pNew.Check(1);
                pNew.mData[pNew.mCount++]={lX1,pTop,l1->r,pBottom};
                lX1=l2->r;
            }
            if(++l1==p1E) return;
            lX1=l1->l;
        }
    }
    
    pNew.Check(1);
    pNew.mData[pNew.mCount++]={lX1,pTop,l1->r,pBottom};

    copy_band(++l1,p1E,pNew,pTop,pBottom);
}

static inline void intersect_band(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E,CNewRegion &pNew,
                              int pTop,int pBottom)
{
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    while(l1!=p1E&&l2!=p2E)
    {
        int lX1=std::max(l1->l,l2->l);
        int lX2=std::min(l1->r,l2->r);
        
        if(lX1<lX2)
        {
            pNew.Check(1);
            pNew.mData[pNew.mCount++]={lX1,pTop,lX2,pBottom};
        }
        
        if(l1->r<l2->r)
        {
            l1++;
        }
        else if(l2->r<l1->r)
        {
            l2++;
        }
        else
        {
            l1++;
            l2++;
        }
    }
}

static inline void xor_band(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E,CNewRegion &pNew,
                              int pTop,int pBottom)
{
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    
    int lXRight=std::min(l1->l,l2->l);
    
    bool lAdded=false;
    
    while(l1!=p1E&&l2!=p2E)
    {
        if(l1->l<l2->l)
        {
            int lLeft=std::max(l1->l,lXRight);
            int lRight=std::min(l1->r,l2->l);
            
            if(lLeft!=lRight)
                union_rect(CRect_i(lLeft,pTop,lRight,pBottom),pNew,lAdded);
        }
        else if(l2->l<l1->l)
        {
            int lLeft=std::max(l2->l,lXRight);
            int lRight=std::min(l2->r,l1->l);
            
            if(lLeft!=lRight)
                union_rect(CRect_i(lLeft,pTop,lRight,pBottom),pNew,lAdded);
        }
        
        //Check if we've found an intersecting band. This will be the case yf lYBot>lYTop
        lXRight=std::min(l1->r,l2->r);
        
        //If we are done with the band (b==lYBot) skip forward to the next band
        if(l1->r==lXRight)
        {
            l1++;
        }
        if(l2->r==lXRight)
        {
            l2++;
        }
    }
    
    if(l1!=p1E)
    {
        union_rect(CRect_i(std::max(l1->l,lXRight),pTop,l1->r,pBottom),pNew,lAdded);
        
        while(++l1!=p1E)
            union_rect(CRect_i(std::max(l1->l,lXRight),pTop,l1->r,pBottom),pNew,lAdded);
    }
    else if(l2!=p2E)
    {
        union_rect(CRect_i(std::max(l2->l,lXRight),pTop,l2->r,pBottom),pNew,lAdded);
        
        while(++l2!=p2E)
            union_rect(CRect_i(std::max(l2->l,lXRight),pTop,l2->r,pBottom),pNew,lAdded);
    }
}

static CNewRegion do_union(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E)
{
    //some rough estimation for capacity... if it's not enough, more will be allocated
    CNewRegion lNew(2*std::max(p1E-p1B,p2E-p2B));
    
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    
    //mark the bottom of previous outputted band
    int lYBottom=std::min(l1->t,l2->t);
    int lYTop;

    //Mark the start of the previous band, so that different bands can be coalesced into a larger band, by using
    //the coalesce_bands function. In the beginning, there is no previous band, so lPrevBand==lCurBand==0.
    std::size_t lPrevBand=0;
    std::size_t lCurBand=0;

    //The algorithm proceeds one source-band at a time. l1BandEnd and l2BandEnd mark the rectangle after the
    //last one in the current band for each region
    const CRect_i *l1BandEnd=band_end(l1,p1E);
    const CRect_i *l2BandEnd=band_end(l2,p2E);

    do
    {
        //Handle bands that don't intersect, if there is any.
        //This pays attention to a single band in the non-intersecting region, so if there are n bands between
        //the current position and the next time it overlaps, the entire loop will be passed n times
        if(l1->t<l2->t)
        {
            int lTop=std::max(l1->t,lYBottom);
            int lBottom=std::min(l1->b,l2->t);
            
            if(lTop!=lBottom)
            {
                copy_band(l1,l1BandEnd,lNew,lTop,lBottom);
                coalesce(lNew,lPrevBand,lCurBand);
            }
            
            lYTop=l2->t;
        }
        else if(l2->t<l1->t)
        {
            int lTop=std::max(l2->t,lYBottom);
            int lBottom=std::min(l2->b,l1->t);
            
            if(lTop!=lBottom)
            {
                copy_band(l2,l2BandEnd,lNew,lTop,lBottom);
                coalesce(lNew,lPrevBand,lCurBand);
            }
            
            lYTop=l1->t;
        }
        else
        {
            lYTop=l1->t;
        }
        
        //Check if we've found an intersecting band. This will be the case yf lYBot>lYTop
        lYBottom=std::min(l1->b,l2->b);
        
        if(lYBottom>lYTop)
        {
            union_band(l1,l1BandEnd,l2,l2BandEnd,lNew,lYTop,lYBottom);
            coalesce(lNew,lPrevBand,lCurBand);
        }
        
        //If we are done with the band (b==lYBot) skip forward to the next band
        if(l1->b==lYBottom)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
        }
        if(l2->b==lYBottom)
        {
            l2=l2BandEnd;
            l2BandEnd=band_end(l2,p2E);
        }
    } while(l1!=p1E&&l2!=p2E);

    //Deal with the region (if any) that still has rectangles
    if(l1!=p1E)
    {
        copy_band(l1,l1BandEnd,lNew,std::max(l1->t,lYBottom),l1->b);
        coalesce(lNew,lPrevBand,lCurBand);
        
        while(l1BandEnd!=p1E)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
            copy_band(l1,l1BandEnd,lNew,std::max(l1->t,lYBottom),l1->b);
        }
    }
    else if(l2!=p2E)
    {
        copy_band(l2,l2BandEnd,lNew,std::max(l2->t,lYBottom),l2->b);
        coalesce(lNew,lPrevBand,lCurBand);
        
        while(l2BandEnd!=p2E)
        {
            l2=l2BandEnd;
            l2BandEnd=band_end(l2,p2E);
            copy_band(l2,l2BandEnd,lNew,std::max(l2->t,lYBottom),l2->b);
        }
    }
    return lNew;
}

static CNewRegion do_subtract(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E)
{
    //some rough estimation for capacity... if it's not enough, more will be allocated
    CNewRegion lNew(2*std::max(p1E-p1B,p2E-p2B));
    
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    
    //mark the bottom of previous outputted band
    int lYBottom=std::min(l1->t,l2->t);
    int lYTop;

    //Mark the start of the previous band, so that different bands can be coalesced into a larger band, by using
    //the coalesce_bands function. In the beginning, there is no previous band, so lPrevBand==lCurBand==0.
    std::size_t lPrevBand=0;
    std::size_t lCurBand=0;

    //The algorithm proceeds one source-band at a time. l1BandEnd and l2BandEnd mark the rectangle after the
    //last one in the current band for each region
    const CRect_i *l1BandEnd=band_end(l1,p1E);
    const CRect_i *l2BandEnd=band_end(l2,p2E);

    do
    {
        //Handle bands that don't intersect, if there is any.
        //This pays attention to a single band in the non-intersecting region, so if there are n bands between
        //the current position and the next time it overlaps, the entire loop will be passed n times
        if(l1->t<l2->t)
        {
            int lTop=std::max(l1->t,lYBottom);
            int lBottom=std::min(l1->b,l2->t);
            
            if(lTop!=lBottom)
            {
                copy_band(l1,l1BandEnd,lNew,lTop,lBottom);
                coalesce(lNew,lPrevBand,lCurBand);
            }
            
            lYTop=l2->t;
        }
        else
        {
            lYTop=l1->t;
        }
        
        //Check if we've found an intersecting band. This will be the case yf lYBot>lYTop
        lYBottom=std::min(l1->b,l2->b);
        
        if(lYBottom>lYTop)
        {
            subtract_band(l1,l1BandEnd,l2,l2BandEnd,lNew,lYTop,lYBottom);
            coalesce(lNew,lPrevBand,lCurBand);
        }
        
        //If we are done with the band (b==lYBot) skip forward to the next band
        if(l1->b==lYBottom)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
        }
        if(l2->b==lYBottom)
        {
            l2=l2BandEnd;
            l2BandEnd=band_end(l2,p2E);
        }
    } while(l1!=p1E&&l2!=p2E);

    //Deal with the region (if any) that still has rectangles
    if(l1!=p1E)
    {
        copy_band(l1,l1BandEnd,lNew,std::max(l1->t,lYBottom),l1->b);
        coalesce(lNew,lPrevBand,lCurBand);
        
        while(l1BandEnd!=p1E)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
            copy_band(l1,l1BandEnd,lNew,std::max(l1->t,lYBottom),l1->b);
        }
    }
    
    return lNew;
}

static CNewRegion do_intersect(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E)
{
    //some rough estimation for capacity... if it's not enough, more will be allocated
    CNewRegion lNew(2*std::max(p1E-p1B,p2E-p2B));
    
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    
    //mark the bottom of previous outputted band
    int lYBottom=std::min(l1->t,l2->t);
    int lYTop;

    //Mark the start of the previous band, so that different bands can be coalesced into a larger band, by using
    //the coalesce_bands function. In the beginning, there is no previous band, so lPrevBand==lCurBand==0.
    std::size_t lPrevBand=0;
    std::size_t lCurBand=0;

    //The algorithm proceeds one source-band at a time. l1BandEnd and l2BandEnd mark the rectangle after the
    //last one in the current band for each region
    const CRect_i *l1BandEnd=band_end(l1,p1E);
    const CRect_i *l2BandEnd=band_end(l2,p2E);

    do
    {
        //Handle bands that don't intersect, if there is any.
        //This pays attention to a single band in the non-intersecting region, so if there are n bands between
        //the current position and the next time it overlaps, the entire loop will be passed n times
        if(l1->t<l2->t)
        {
            lYTop=l2->t;
        }
        else
        {
            lYTop=l1->t;
        }
        
        //Check if we've found an intersecting band. This will be the case yf lYBot>lYTop
        lYBottom=std::min(l1->b,l2->b);
        
        if(lYBottom>lYTop)
        {
            intersect_band(l1,l1BandEnd,l2,l2BandEnd,lNew,lYTop,lYBottom);
            coalesce(lNew,lPrevBand,lCurBand);
        }
        
        //If we are done with the band (b==lYBot) skip forward to the next band
        if(l1->b==lYBottom)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
        }
        if(l2->b==lYBottom)
        {
            l2=l2BandEnd;
            l2BandEnd=band_end(l2,p2E);
        }
    } while(l1!=p1E&&l2!=p2E);

    return lNew;
}

static CNewRegion do_xor(const CRect_i *p1B,const CRect_i *p1E,const CRect_i *p2B,const CRect_i *p2E)
{
    //some rough estimation for capacity... if it's not enough, more will be allocated
    CNewRegion lNew(2*std::max(p1E-p1B,p2E-p2B));
    
    const CRect_i *l1=p1B;
    const CRect_i *l2=p2B;
    
    //mark the bottom of previous outputted band
    int lYBottom=std::min(l1->t,l2->t);
    int lYTop;

    //Mark the start of the previous band, so that different bands can be coalesced into a larger band, by using
    //the coalesce_bands function. In the beginning, there is no previous band, so lPrevBand==lCurBand==0.
    std::size_t lPrevBand=0;
    std::size_t lCurBand=0;

    //The algorithm proceeds one source-band at a time. l1BandEnd and l2BandEnd mark the rectangle after the
    //last one in the current band for each region
    const CRect_i *l1BandEnd=band_end(l1,p1E);
    const CRect_i *l2BandEnd=band_end(l2,p2E);

    do
    {
        //Handle bands that don't intersect, if there is any.
        //This pays attention to a single band in the non-intersecting region, so if there are n bands between
        //the current position and the next time it overlaps, the entire loop will be passed n times
        if(l1->t<l2->t)
        {
            int lTop=std::max(l1->t,lYBottom);
            int lBottom=std::min(l1->b,l2->t);
            
            if(lTop!=lBottom)
            {
                copy_band(l1,l1BandEnd,lNew,lTop,lBottom);
                coalesce(lNew,lPrevBand,lCurBand);
            }
            
            lYTop=l2->t;
        }
        else if(l2->t<l1->t)
        {
            int lTop=std::max(l2->t,lYBottom);
            int lBottom=std::min(l2->b,l1->t);
            
            if(lTop!=lBottom)
            {
                copy_band(l2,l2BandEnd,lNew,lTop,lBottom);
                coalesce(lNew,lPrevBand,lCurBand);
            }
            
            lYTop=l1->t;
        }
        else
        {
            lYTop=l1->t;
        }
        
        //Check if we've found an intersecting band. This will be the case yf lYBot>lYTop
        lYBottom=std::min(l1->b,l2->b);
        
        if(lYBottom>lYTop)
        {
            xor_band(l1,l1BandEnd,l2,l2BandEnd,lNew,lYTop,lYBottom);
            coalesce(lNew,lPrevBand,lCurBand);
        }
        
        //If we are done with the band (b==lYBot) skip forward to the next band
        if(l1->b==lYBottom)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
        }
        if(l2->b==lYBottom)
        {
            l2=l2BandEnd;
            l2BandEnd=band_end(l2,p2E);
        }
    } while(l1!=p1E&&l2!=p2E);

    //Deal with the region (if any) that still has rectangles
    if(l1!=p1E)
    {
        copy_band(l1,l1BandEnd,lNew,std::max(l1->t,lYBottom),l1->b);
        coalesce(lNew,lPrevBand,lCurBand);
        
        while(l1BandEnd!=p1E)
        {
            l1=l1BandEnd;
            l1BandEnd=band_end(l1,p1E);
            copy_band(l1,l1BandEnd,lNew,std::max(l1->t,lYBottom),l1->b);
        }
    }
    else if(l2!=p2E)
    {
        copy_band(l2,l2BandEnd,lNew,std::max(l2->t,lYBottom),l2->b);
        coalesce(lNew,lPrevBand,lCurBand);
        
        while(l2BandEnd!=p2E)
        {
            l2=l2BandEnd;
            l2BandEnd=band_end(l2,p2E);
            copy_band(l2,l2BandEnd,lNew,std::max(l2->t,lYBottom),l2->b);
        }
    }
    return lNew;
}

static inline CRect_i calc_bbox(const CNewRegion &pNew)
{
    if(pNew.mCount==0)
    {
        return CRect_i(0,0,0,0);
    }
    else if(pNew.mCount==1)
    {
        return pNew.mData[0];
    }
        
    const CRect_i *lFirst=pNew.mData;
    const CRect_i *lLast=pNew.mData+pNew.mCount-1;
    
    CRect_i lBBox(std::min(lFirst->l,lLast->l),lFirst->t,std::max(lFirst->r,lLast->r),lLast->b);

    for(++lFirst;lFirst!=lLast;++lFirst)
    {
        if(lFirst->l<lBBox.l) lBBox.l=lFirst->l;
        if(lFirst->r>lBBox.r) lBBox.r=lFirst->r;
    }
    
    return lBBox;
}

CRegion::CRegion(const CRegion &pRH)
    :   mBBox(pRH.mBBox)
    ,   mCount(pRH.mCount)
{
    if(mCount>1)
        mData=dup_array(pRH.mData,mCount);
    else
        mData=&mBBox;
}

bool CRegion::Contains(const CPoint_i &pPoint) const
{
    if(!mBBox.Contains(pPoint)) return false;

    for(int i=0;i<mCount;i++)
    {
        if(mData[i].Contains(pPoint)) return true;
    }

    return false;
}

void CRegion::Offset(const CPoint_i &pOffset)
{
    for(int i=0;i<mCount;i++)
        mData[i]+=pOffset;
    
    if(mData!=&mBBox)
        mBBox+=pOffset;
}

CRegion &CRegion::operator=(const CRegion &pOther)
{
    if(this==&pOther) return *this;

    mBBox=pOther.mBBox;

    if(pOther.mCount<=1)
    {
        if(mData!=&mBBox) free(mData);
        mData=&mBBox;
    }
    else
    {
        if(mData!=&mBBox)
        {
            if(mCount<pOther.mCount)
            {
                free(mData);
                mData=alloc_array<CRect_i>(pOther.mCount);
            }
        }
        else
        {
            mData=alloc_array<CRect_i>(pOther.mCount);
        }

        copy_array(pOther.mData,mData,pOther.mCount);
    }

    mCount=pOther.mCount;

    return *this;
}

CRegion &CRegion::operator=(const CRect_i &pRect)
{
    if(mData!=&mBBox)
        free(mData);
        
    mBBox=pRect;
    mData=&mBBox;
    mCount=1;
    
    return *this;
}

bool CRegion::operator==(const CRegion &pRH) const
{
    if(mCount!=pRH.mCount) return false;
    if(mCount==0) return true;
    if(mBBox!=pRH.mBBox) return false;
    if(mCount==1) return true;

    for(int i=0;i<mCount;i++)
    {
        if(mData[i]!=pRH.mData[i])
            return false;
    }
    
    return true;
}

CRegion &CRegion::operator|=(const CRegion &pRH)
{
    //check for all simple cases
    if(this==&pRH||!pRH.mCount)
        return *this;
    if(!mCount)
        return *this=pRH;
    if(mCount==1&&mBBox.Contains(pRH.mBBox))
        return *this;
    if(pRH.mCount==1&&pRH.mBBox.Contains(mBBox))
        return *this=pRH.mBBox;

    CNewRegion lNew=do_union(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);

    *this=CRegion(CRect_i(std::min(mBBox.l,pRH.mBBox.l),std::min(mBBox.t,pRH.mBBox.t),
                            std::max(mBBox.r,pRH.mBBox.r),std::max(mBBox.b,pRH.mBBox.b)),
                   lNew.mData,lNew.mCount);
    
    return *this;
}

CRegion &CRegion::operator|=(const CRect_i &pRH)
{
    //check for all simple cases
    if(!mCount||pRH.Contains(mBBox))
        return *this=pRH;
    if(mCount==1&&mBBox.Contains(pRH))
        return *this;

    CNewRegion lNew=do_union(mData,mData+mCount,&pRH,&pRH+1);

    *this=CRegion(CRect_i(std::min(mBBox.l,pRH.l),std::min(mBBox.t,pRH.t),
                            std::max(mBBox.r,pRH.r),std::max(mBBox.b,pRH.b)),
                   lNew.mData,lNew.mCount);
    
    return *this;
}

CRegion &CRegion::operator-=(const CRegion &pRH)
{
    if(this==&pRH)
    {
        clear();
        return *this;
    }
    if(!mCount||!pRH.mCount||!mBBox.DoesIntersect(pRH.mBBox))
        return *this;
    if(pRH.mCount==1&&pRH.mBBox.Contains(mBBox))
    {
        clear();
        return *this;
    }
    
    CNewRegion lNew=do_subtract(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);
    
    return *this=CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion &CRegion::operator-=(const CRect_i &pRH)
{
    if(!mCount||!mBBox.DoesIntersect(pRH))
        return *this;
    if(pRH.Contains(mBBox))
    {
        clear();
        return *this;
    }
    
    CNewRegion lNew=do_subtract(mData,mData+mCount,&pRH,&pRH+1);
    
    return *this=CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion &CRegion::operator&=(const CRegion &pRH)
{
    //check for all simple cases
    if(this==&pRH)
        return *this;
    if(!mCount||!pRH.mCount||!mBBox.DoesIntersect(pRH.mBBox))
    {
        clear();
        return *this;
    }
    if(mCount==1&&mBBox.Contains(pRH.mBBox))
    {
        *this=pRH;
        return *this;
    }
    if(pRH.mCount==1&&pRH.mBBox.Contains(mBBox))
    {
        return *this;
    }

    CNewRegion lNew=do_intersect(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);
    
    return *this=CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion &CRegion::operator&=(const CRect_i &pRH)
{
    //check for all simple cases
    if(!mCount||!mBBox.DoesIntersect(pRH))
    {
        clear();
        return *this;
    }
    if(mCount==1&&mBBox.Contains(pRH))
    {
        *this=pRH;
        return *this;
    }
    if(pRH.Contains(mBBox))
    {
        return *this;
    }

    CNewRegion lNew=do_intersect(mData,mData+mCount,&pRH,&pRH+1);
    
    return *this=CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion CRegion::operator|(const CRect_i &pRH) const
{
    //check for all simple cases
    if(!mCount)
        return CRegion(pRH);
    if(mCount==1&&mBBox.Contains(pRH))
        return *this;
    if(pRH.Contains(mBBox))
        return CRegion(pRH);

    CNewRegion lNew=do_union(mData,mData+mCount,&pRH,&pRH+1);

    return CRegion(CRect_i(std::min(mBBox.l,pRH.l),std::min(mBBox.t,pRH.t),
                            std::max(mBBox.r,pRH.r),std::max(mBBox.b,pRH.b)),
                   lNew.mData,lNew.mCount);
}

CRegion CRegion::operator|(const CRegion &pRH) const
{
    //check for all simple cases
    if(this==&pRH||!pRH.mCount)
        return *this;
    if(!mCount)
        return pRH;
    if(mCount==1&&mBBox.Contains(pRH.mBBox))
        return *this;
    if(pRH.mCount==1&&pRH.mBBox.Contains(mBBox))
        return pRH;

    CNewRegion lNew=do_union(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);

    return CRegion(CRect_i(std::min(mBBox.l,pRH.mBBox.l),std::min(mBBox.t,pRH.mBBox.t),
                            std::max(mBBox.r,pRH.mBBox.r),std::max(mBBox.b,pRH.mBBox.b)),
                   lNew.mData,lNew.mCount);
}

CRegion CRegion::operator-(const CRect_i &pRH) const
{
    //check for all simple cases
    if(!mCount||!mBBox.DoesIntersect(pRH))
        return *this;
    if(pRH.Contains(mBBox))
        return CRegion();
    
    CNewRegion lNew=do_subtract(mData,mData+mCount,&pRH,&pRH+1);
    
    return CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion CRegion::operator-(const CRegion &pRH) const
{
    //check for all simple cases
    if(this==&pRH)
        return CRegion();
    if(!mCount||!pRH.mCount||!mBBox.DoesIntersect(pRH.mBBox))
        return *this;
    if(pRH.mCount==1&&pRH.mBBox.Contains(mBBox))
        return CRegion();
    
    CNewRegion lNew=do_subtract(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);
    
    return CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion CRegion::operator&(const CRect_i &pRH) const
{
    //check for all simple cases
    if(!mCount||!mBBox.DoesIntersect(pRH))
        return CRegion();
    if(mCount==1&&mBBox.Contains(pRH))
        return CRegion(pRH);
    if(pRH.Contains(mBBox))
        return *this;

    CNewRegion lNew=do_intersect(mData,mData+mCount,&pRH,&pRH+1);
    
    return CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion CRegion::operator&(const CRegion &pRH) const
{
    //check for all simple cases
    if(this==&pRH)
        return *this;
    if(!mCount||!pRH.mCount||!mBBox.DoesIntersect(pRH.mBBox))
        return CRegion();
    if(mCount==1&&mBBox.Contains(pRH.mBBox))
        return pRH;
    if(pRH.mCount==1&&pRH.mBBox.Contains(mBBox))
        return *this;

    CNewRegion lNew=do_intersect(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);
    
    return CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion CRegion::operator^(const CRect_i &pRH) const
{
    //check for all simple cases
    if(!mCount)
        return CRegion(pRH);

    CNewRegion lNew=do_xor(mData,mData+mCount,&pRH,&pRH+1);
    
    return CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

CRegion CRegion::operator^(const CRegion &pRH) const
{
    //check for all simple cases
    if(!mCount)
        return pRH;
    if(!pRH.mCount)
        return *this;

    CNewRegion lNew=do_xor(mData,mData+mCount,pRH.mData,pRH.mData+pRH.mCount);
    
    return CRegion(calc_bbox(lNew),lNew.mData,lNew.mCount);
}

/*namespace buola*/ }
